package com.zhugang.week10;

/**
 * @program algorithms
 * @description: coinChange
 * @author: chanzhugang
 * @create: 2022/08/29 15:14
 */
public class CoinChange {

    /**
     * 322 零钱兑换
     * 完全背包问题
     *
     * @param coins
     * @param amount
     * @return
     */
    public int coinChange(int[] coins, int amount) {
        // 凑成总金额最少硬币个数
        // 完全背包问题（最优问题）：最少需要多少物品能填满背包
        int n = coins.length;
        // 第i个硬币决策完后，凑足金额j需要的最少硬币数
        int[][] dp = new int[n][amount + 1];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j <= amount; j++) {
                // 初始化：求最小值是设置为最大值
                dp[i][j] = Integer.MAX_VALUE;
            }
        }
        // 初始化第一行
        for (int c = 0; c <= amount / coins[0]; c++) {
            // 第一个硬币可以有0个、1个、.....c个
            dp[0][c * coins[0]] = c;
        }

        for (int i = 1; i < n; i++) {
            for (int j = 0; j <= amount; j++) {
                // 硬币个数
                int k = j / coins[i];
                for (int c = 0; c <= k; c++) {
                    if (dp[i - 1][j - c * coins[i]] != Integer.MAX_VALUE) {
                        // 最小值
                        dp[i][j] = Math.min(dp[i][j], dp[i - 1][j - c * coins[i]] + c);
                    }
                    // 两种写法都可以
                   /* if (dp[i - 1][j - c * coins[i]] != Integer.MAX_VALUE && dp[i - 1][j - c * coins[i]] + c < dp[i][j]) {
                        // 可达
                        dp[i][j] = dp[i - 1][j - c * coins[i]] + c;
                    }*/
                }
            }
        }
        if (dp[n - 1][amount] == Integer.MAX_VALUE) {
            return -1;
        }
        return dp[n - 1][amount];
    }
}